前言

昨天跟大家介紹了遞迴的概念，以及在階乘的實際應用，今天要來接著繼續介紹，如果還不太熟悉的可以看一下前一天的文章喔！

費氏數列 Fibonacci sequence

在數學上，費波那契數是以遞迴的方法來定義：

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n+1)

每一項都是前兩項的和，0 為第 0 項，不是第 1 項！
底下為前幾項費氏數列的值

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ,610, 987……

def Fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return Fibonacci(n - 2) + Fibonacci(n - 1)
for i in range(10):
    print(Fibonacci(i), end = ' ')

在上面的程式中，一個函式就呼叫自己兩次，然後每次呼叫都會佔用到記憶體的空間，只做小數字的話還好，但是如果運算到數字非常大的時候，每個函式會再呼叫兩個函式，這樣疊加下來就會耗費非常多的時間。

計算 f(n) 會用到 f(n-1) 和 f(n-2)，然後 f(n-1) 會再用到 f(n-2) 和 f(n-3)，所以 f(n-2) 就會被呼叫兩次，最後的 f(1) 和 f(0) 會被瘋狂呼叫，狂佔記憶體，浪費時間也浪費空間。

Recursion 的限制

如果程式設計不佳，導致無窮迴圈或是跑的次數太多，電腦的記憶體就會被塞滿，所以為了防止這件事情，Python 對於遞迴有次數限制，預設的次數可以透過 sys 這個 module 的函式來查看，預設為 3000，若超過這個次數會出現 RecursionError: maximum recursion depth exceeded 的 error

import sys
sys.getrecursionlimit()

待續...